/* 试给出自下而上从右到左的层次遍历 */
#include <iostream>
#include "BiTreefun.h"
using namespace std;
#define maxsize 50

// 层次遍历 逆序版
void level(BTNode *p)
{
  // 创建栈
  BTNode *stack[maxsize];
  int top = -1;
  
  // 创建队列
  int front = 0, rear = 0;
  BTNode *que[maxsize];
  
  // 如果访问元素不为空
  if (p != NULL)
  {
    // 元素进队列
    que[++rear] = p;
    
    // 如果队列不为空
    while (front != rear)
    {
      // 元素出队列
      p = que[++front];
      
      // 元素进栈
      stack[++top] = p;
      
      // 左孩子进队列
      if (p->lchild != NULL)
        que[++rear] = p->lchild;
      
      // 右孩子进队列
      if (p->rchild != NULL)
        que[++rear] = p->rchild;
    }
  }
  
  // 依次输出栈中元素
  for (int i = top; i > -1; --i)
  {
    cout << stack[i]->data << " ";
  }
}

int main()
{
  // 创建二叉树
  BTNode *T = create_bitree();
  
  // 层次遍历 逆序版
  level(T);
}